6.30 测试

6.30 测试

混氏新子 蒟蒻

前情提要

题目链接

成绩表

成绩表

nice

题解

T1

  • 首先考虑只有一个数的情况。
  • 然后显然没有最后的的数都要乘到有的数中。显然当时模不为的数最少。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int t;
int l, r, k;
int main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &l, &r, &k);
if (l == r) {
if (l == 1) {
puts("NO");
continue;
}
else {
puts("YES");
continue;
}
}
int tmp = (r - l + 1) / 2;
if ((l & 1) && (r & 1)) ++tmp;
puts(k >= tmp ? "YES" : "NO");
}
return 0;
}

T2

#隔板法

直接枚举能够添加到多少,然后你就会发现,之前的数都必须有,要把个数放在前面,但是如果本来的集合里就有的数就可以不用放。你想到了什么?

对!小学奥数中苹果放盘子的问题,用隔板法,那可以放个的还是用经典套路,假设可以空的盘子里面多放一个然后就不会为了(就是加上之前有数的数的个数)。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define N 200010
#define mod 998244353ll
using namespace std;
using ll = long long;
int n, k;
int a[N], s[N];
ll ans;
int tot;
ll fact[N << 1], nifact[N << 1];
inline ll qp(ll x, ll y) {
ll ans = 1;
while (y) {
if (y & 1) ans = ans * x % mod;
y >>= 1;
x = x * x % mod;
}
return ans;
}
inline ll c(ll x, ll y) {
return fact[x] * nifact[y] % mod * nifact[x - y] % mod;
}
int main() {
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
++s[a[i]];
}
fact[0] = 1;
nifact[0] = 1;
for (int i = 1; i <= n + k; ++i) {
fact[i] = fact[i - 1] * i % mod;
nifact[i] = qp(fact[i], mod - 2);
}
for (int i = 0; i < k + tot; ++i) {
ans += c(k + tot - 1, i);
ans %= mod;
// cout << ans << endl;
if (i < N && s[i]) ++tot;
}
printf("%lld", ans);
return 0;
}

T3

#括号匹配

  • 将第一个条件转化一下,就能得到第一个条件,异或相等
  • 第二个条件注意是

很容易想到括号匹配,而且如果有和大于的话如果行的话肯定是相当于右括号,所以想到从右往左用栈。从左往右有问题。

code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define N 10010
using namespace std;
using ll = long long;
int t, n;
ll k;
ll a[N], b[N];
ll stk[N], top;
int main() {
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
scanf("%d", &t);
while (t--) {
scanf("%d%lld", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%lld", a + i);
}
for (int i = 0; i < n; ++i) {
scanf("%lld", b + i);
}
top = 0;
for (int i = n - 1; ~i; --i) {
ll tmp = a[i] ^ b[i];
// cerr << tmp << ' ';
if (top && tmp == stk[top] && a[i] + b[i] <= k) --top;
else {
stk[++top] = tmp;
}
}
// cerr << endl;
if (top) puts("YES");
else puts("NO");
}
return 0;
}

T4

直接输出 -1,10 pts。

可以发现横向移动和纵向移动是解耦的,毫无关联的,所以分别计算加起来就行。

对于横向移动,开一个数组记录值,然后倒着枚举同一时间的激光位置,计算此时这个位置至少走多少步。

但是没写出来……

后记

行吧,可以。

  • 标题: 6.30 测试
  • 作者: 混氏新子
  • 创建于 : 2023-07-02 19:42:54
  • 更新于 : 2023-09-24 19:12:16
  • 链接: https://blog.huasushis.cn/2023/6.30 测试/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
6.30 测试